/*
 * One example for NOI CSP-J Lesson 8:
 * <https://courses.fmsoft.cn/plzs/noijunior-other-data-structures.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>

using namespace std;

// 从下而上制表
size_t min_cost_merging_stones(const vector<unsigned>& stones)
{
    size_t n = stones.size();

    // 初始化从第 0 堆到第 n 堆的总石子表
    // 这样从 i 堆到第 j 堆的石子总数可快速计算：sum[j+1] - sum[i]
    vector<size_t> sum(n + 1, 0);
    for (size_t i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + stones[i - 1];
    }

    // 初始化 dp 表
    vector<vector<size_t>> dp(n, vector<size_t>(n, SIZE_MAX));
    for (size_t i = 0; i < n; i++)
        dp[i][i] = 0;

    for (size_t l = 0; l < n; l++) {
        for (size_t i = 0; i < n - l; i++) {

            size_t j = i + l;
            // 从 k 分界递推
            for (size_t k = i; k < j; k++) {
                size_t sum_i2j = sum[j + 1] - sum[i];
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum_i2j);
            }
        }
    }

    return dp[0][n - 1];
}

int main()
{
    vector<unsigned> stones;
    stones.push_back(1);
    stones.push_back(2);
    stones.push_back(3);

    size_t min_cost = min_cost_merging_stones(stones);
    cout << min_cost << endl;

    assert(min_cost == 9);
    return 0;
}

